Sparse Representation on Graphs by Tight Wavelet Frames and Applications

摘要

In this paper, we introduce a new (constructive) characterization of tightwavelet frames on non-flat domains in both continuum setting, i.e. onmanifolds, and discrete setting, i.e. on graphs; discuss how fast tight waveletframe transforms can be computed and how they can be effectively used toprocess graph data. We start with defining the quasi-affine systems on a givenmanifold $\cM$ that is formed by generalized dilations and shifts of a finitecollection of wavelet functions $\Psi:=\{\psi_j: 1\le j\le r\}\subset L_2(\R)$.We further require that $\psi_j$ is generated by some refinable function $\phi$with mask $a_j$. We present the condition needed for the masks $\{a_j: 0\lej\le r\}$ so that the associated quasi-affine system generated by $\Psi$ is atight frame for $L_2(\cM)$. Then, we discuss how the transition from thecontinuum (manifolds) to the discrete setting (graphs) can be naturally done.In order for the proposed discrete tight wavelet frame transforms to be usefulin applications, we show how the transforms can be computed efficiently andaccurately by proposing the fast tight wavelet frame transforms for graph data(WFTG). Finally, we consider two specific applications of the proposed WFTG:graph data denoising and semi-supervised clustering. Utilizing the sparserepresentation provided by the WFTG, we propose $\ell_1$-norm basedoptimization models on graphs for denoising and semi-supervised clustering. Onone hand, our numerical results show significant advantage of the WFTG over thespectral graph wavelet transform (SGWT) by [1] for both applications. On theother hand, numerical experiments on two real data sets show that the proposedsemi-supervised clustering model using the WFTG is overall competitive with thestate-of-the-art methods developed in the literature of high-dimensional dataclassification, and is superior to some of these methods.